package com.chj.jz.dp.class04;

public class Code08_BackPack {
	/**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public static int backPack(int m, int[] A) {
        // write your code here
    	
    	int n = A.length;
    	if(n == 0) {
    		return 0;
    	}
    	
    	boolean[][] f = new boolean[n + 1][m + 1];
    	int[][] pi = new int[n + 1][m + 1];
    	int i, j;
    	f[0][0] = true;
    	for(i = 1; i <= m; i++) {
    		f[0][i] = false;
    	}
    	
    	for(i = 1; i <= n; i++) {
    		for(j = 0; j <= m; j++) {
    			f[i][j] = f[i - 1][j];
    			pi[i][j] = 0;
    			
    			if(j >= A[i - 1]) {
    				if(f[i - 1][j - A[i - 1]]) {
    					pi[i][j] = 1;
    				}
    				
    				f[i][j] |= f[i - 1][j - A[i - 1]];
    			}
    		}
    	}
    	
    	int res = 0;
    	for(i = m; i >= 0; i--) {
    		if(f[n][i] == true) {
    			res = i;
    			break;
    		}
    	}
    	
    	i = res;
    	for(j = n; j >= 1; j--) {
    		if(pi[j][i] == 1) {
    			System.out.print(A[j - 1] + " ");
    			i -= A[j - 1];
    		}
    	}
    	System.out.println();
    	return res;
    }
    
    public static void main(String[] args) {
		{
			int[] arr = new int[] {3, 4, 8, 5};
			int k = 10;
			System.out.println(backPack(k, arr));
		}
		{
			int[] arr = new int[] {2, 3, 5, 7};
			int k = 12;
			System.out.println(backPack(k, arr));
		}
    }
}
